#include <vector>
using namespace std;

struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 方法一：神奇的分治，时间复杂度O(Nlogk)，且比方法二快
class Solution {
  ListNode *merge2Lists(ListNode *l1, ListNode *l2) {
    ListNode res{0, nullptr}, *tailPtr = &res;
    while (l1 != nullptr && l2 != nullptr) {
      if (l1->val > l2->val) {
        tailPtr->next = l2;
        l2 = l2->next;
      } else {
        tailPtr->next = l1;
        l1 = l1->next;
      }
      tailPtr = tailPtr->next;
    }

    if (l1 != nullptr) {
      tailPtr->next = l1;
    }
    if (l2 != nullptr) {
      tailPtr->next = l2;
    }
    return res.next;
  }

  ListNode *mergeRange(vector<ListNode *> &lists, int left, int right) {
    if (left == right) {
      return lists[left];
    }
    if (left + 1 == right) {
      return merge2Lists(lists[left], lists[right]);
    }
    int mid = (left + right) >> 1;
    ListNode *leftList = mergeRange(lists, left, mid),
             *rightList = mergeRange(lists, mid + 1, right);
    return merge2Lists(leftList, rightList);
  }

public:
  ListNode *mergeKLists(vector<ListNode *> &lists) {
    if (lists.size() == 0) {
      return nullptr;
    }
    return mergeRange(lists, 0, lists.size() - 1);
  }
};

// 方法二：优先队列，时间复杂度O(Nlogk)
class Solution {
  static bool compare(const ListNode *a, const ListNode *b) {
    return a->val > b->val;
  }

public:
  ListNode *mergeKLists(vector<ListNode *> &lists) {
    ListNode resHead{0, nullptr}, *resTailPtr = &resHead;

    priority_queue<ListNode *, vector<ListNode *>, decltype(this->compare)> pq(
        this->compare);

    for (auto ptr : lists) {
      if (ptr != nullptr) {
        pq.push(ptr);
      }
    }

    while (pq.size() != 0) {
      resTailPtr->next = pq.top();
      resTailPtr = resTailPtr->next;
      pq.pop();
      if (resTailPtr->next != nullptr) {
        pq.push(resTailPtr->next);
      }
    }
    return resHead.next;
  }
};
